import java.util.Arrays;

public class RadixSort {
    private static void radixSortFunc(int[] array,int maxDigit){
        int mode = 10 ; // 十进制
        int divide = 1;// 将 数值上的每个数“分割”，方便获取数据的一个位上的值

        // 每个数据从个位到最大值的最高位，按照其位上的大小 放出 拿出
        for (int i = 0; i < maxDigit; i++,mode *= 10,divide *=10) {
            // 考虑 负数的 情况，0~9 对应负数，10 ~ 19 对应正数
            // 行 对应的是编号， 列 对应的存储的数据
            int[][] counter = new int[mode*2][0];

            for (int j = 0; j < array.length; j++) {
                int number = ((array[j] % mode)/divide) + mode; /*获取 数据对应 空间的编号 */
                counter[number] = arrayAppend(counter[number],array[j]);
            }
            int pos = 0;
            for (int[] number:counter) {
                for (int val:number) {
                    array[pos++] = val;
                }
            }
        }
    }
    private static int[] arrayAppend(int[] arr,int value){
        arr = Arrays.copyOf(arr,arr.length+1);
        arr[arr.length-1] = value;
        return  arr;
    }

    public static void radixSort(int[] array){
        int maxNumLength = getNumLength(array);
       radixSortFunc(array,maxNumLength);
    }
    // 获取最大值的位数 - 功能“窗口”
    private static int getNumLength(int[] array){
        int maxVal = getMaxValue(array);
        return getMaxDigit(maxVal);
    }
    //获取最大值
    private static int getMaxValue(int[] array){
        int maxValue= array[0];
        for (int value: array) {
            if(value > maxValue){
                maxValue = value;
            }
        }
        return maxValue;
    }
    // 获取最大值的位数 - 执行
    private static int getMaxDigit(int num){
        if(num == 0){
            return 0;
        }
        int len = 0;
        while(num > 0){
            len++;
            num /= 10;
        }
        return len;
    }

    public static void main(String[] args) {
        int[] array = {124,366,170,52,200,78,468};
        radixSort(array);
        System.out.println(Arrays.toString(array));
    }
}
